package com.kaizen.leet448;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
 *
 * 找到所有在 [1, n] 范围之间没有出现在数组中的数字。
 *
 * 您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
 *
 * 示例:
 *
 * 输入:
 * [4,3,2,7,8,2,3,1]
 *
 * 输出:
 * [5,6]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author undi
 * @date 2020/5/15
 */
public class SolutionUndi {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1};
        System.out.println(findDisappearedNumbers(nums));
    }

    /**
     * 思路1：创建一个 List，存储 1--n，创建一个返回 List，存储
     * 循环的时候跟 i 值相等的 nums[i]，判断包含关系
     * 消耗太大，操作太复杂
     * ======================
     * 思路2：使用 Set，Set 不存储重复的数据
     * 执行用时 :
     * 28 ms
     * , 在所有 Java 提交中击败了
     * 11.88%
     * 的用户
     * 内存消耗 :
     * 48.3 MB
     * , 在所有 Java 提交中击败了
     * 66.67%
     * 的用户
     *
     * @param nums
     * @return
     */
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        //存放出现过的数字 nums[i],重复出现将覆盖
        Set<Integer> hashset = new HashSet<>();
        //存放 返回结果
        List<Integer> list = new ArrayList<>();

        //遍历数组，添加到hashset
        for (int i = 0; i < nums.length; i++) {
            hashset.add(nums[i]);
        }

        //将没出现的数字添加到list
        for (int i = 1; i <= nums.length; i++) {
            if (hashset.contains(i)) {
            }
            else{
                list.add(i);
            }
        }
        return list;
    }
}
